﻿#define _CRT_SECURE_NO_WARNINGS


#include <stdio.h>

//int main()
//{
//	int num = -10;
//	int n = num << 1;
//	//原码  10000000000000000000000000001010
//	//反码  11111111111111111111111111110101
//	//补码  11111111111111111111111111110110
//	//<< 1  11111111111111111111111111101100
// //取反+1 10000000000000000000000000000100
//	printf("n= %d\n", n);//-20
//	printf("num= %d\n", num);
//	return 0;
//}


//#include <stdio.h>
//int main()
//{
//	int num = -10;
//	int n = num >> 1;
//	//原码  10000000000000000000000000001010
//	//反码  11111111111111111111111111110101
//	//补码  11111111111111111111111111110110
//	//>> 1  11111111111111111111111111111011
//   //取反+1 10000000000000000000000000000101
//	printf("n= %d\n", n);//-5
//	printf("num= %d\n", num);
//	return 0;
//}

//
//int main()
//{
//	int a = 10;
//	int b = a << -1;
//	return 0;
//}


//int main()
//{
//	int a = 10;
//	int b = -10;
//	int c;
//	
//	int i = 0;
//	for ( i = 0; i < 4; i++)
//	{
//		c = a << i;
//		printf("%d ", c);
//		
//	}
//	printf("\n");
//	for ( i = 0; i < 4; i++)
//	{
//		c = b << i;
//		printf("%d ", c);
//	}
//	printf("\n");
//	for (int i = 0; i < 4; i++)
//	{
//		c = a >> i;
//		printf("%d ", c);
//
//	}
//	printf("\n");
//	for ( i = 0; i < 4; i++)
//	{
//		c = b >> i;
//		printf("%d ", c);
//	}
//	return 0;
//}
//
//#include <stdio.h>
//int main()
//{
//	//0  00000000000000000000000000000000
//	//~0 11111111111111111111111111111111
//
//	printf("%d\n", ~0);//-1
//	return 0;
//}


//
//#include <stdio.h>
//int main()
//{
//	int num1 = -3;
//	int num2 = 5;
//	printf("%d\n", num1 & num2);
//	printf("%d\n", num1 | num2);
//	printf("%d\n", num1 ^ num2);
//	printf("%d\n", ~0);
//	return 0;
//}

//
//#include <stdio.h>
//int main()
//{
//	int a = 10;
//	int b = 20;
//	a = a ^ b;
//	b = a ^ b;
//	a = a ^ b;
//	printf("a = %d b = %d\n", a, b);
//	return 0;
//}


////⽅法1
//#include <stdio.h>
//int main()
//{
//	int num = 10;
//	int count = 0;//计数
//	while (num)
//	{
//		if (num % 2 == 1)
//			count++;
//		num = num / 2;
//	}
//	printf("⼆进制中1的个数 = %d\n", count);
//	return 0;
//}

////⽅法2：
//#include <stdio.h>
//int main()
//{
//	int num = -1;
//	int i = 0;
//	int count = 0;//计数
//	for (i = 0; i < 32; i++)
//	{
//		if (num & (1 << i))
//			count++;
//	}
//	printf("⼆进制中1的个数 = %d\n", count);
//	return 0;
//}


//⽅法3：
//#include <stdio.h>
//int main()
//{
//	int num = -1;
//	int i = 0;
//	int count = 0;//计数
//	while (num)
//	{
//		count++;
//		num = num & (num - 1);
//	}
//	printf("⼆进制中1的个数 = %d\n", count);
//	return 0;
//}



#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//
//
//typedef int StackData;
//
//typedef struct stack
//{
//    StackData* data;
//    int top;
//    int capcity;
//}stack;
//
////栈初始化
//void StackInit(stack* ps)
//{
//    assert(ps);
//    ps->data = NULL;
//    ps->top = -1;
//    ps->capcity = 0;
//}
//
////压栈
//void StackPush(stack* ps, StackData x)
//{
//    assert(ps);
//    if (ps->top + 1 == ps->capcity)
//    {
//        ps->capcity = ps->capcity == 0 ? 4 : ps->capcity * 2;
//        StackData* pmid = (StackData*)realloc(ps->data, (ps->capcity) * sizeof(StackData));
//        if (pmid == NULL)
//        {
//            perror("Push::relloc");
//            return;
//        }
//        ps->data = pmid;
//
//    }
//    ++(ps->top);
//    ps->data[ps->top] = x;
//}
//
////出栈
//void StackPop(stack* ps)
//{
//    assert(ps && ps->top != -1);
//    ps->top--;
//}
//
////栈顶元素
//StackData StackTop(stack* ps)
//{
//    assert(ps && ps->top != -1);
//    return ps->data[ps->top];
//}
//
////栈底元素
//StackData StackBot(stack* ps)
//{
//    assert(ps && ps->top != -1);
//    return ps->data[0];
//}
//
////有效元素个数
//int StackSize(stack* ps)
//{
//    assert(ps);
//    return ps->top + 1;
//}
//
////判空
//int StackEmpty(stack* ps)
//{
//    assert(ps);
//    if (StackSize(ps) == 0)
//        return 1;
//    else
//        return 0;
//}
//
//// 销毁栈 
//void StackDestroy(stack* ps)
//{
//    assert(ps);
//    free(ps->data);
//}
//
//
//typedef struct {
//    stack a;
//    stack b;
//
//    int size;
//
//} MyQueue;
//
//
//MyQueue* myQueueCreate() {
//
//    //创建队列
//    MyQueue* NewQueue = (MyQueue*)malloc(sizeof(MyQueue));
//    if (NewQueue == NULL)
//    {
//        perror("myQueueCreate::malloc");
//        return NULL;
//    }
//
//    //初始化队列
//    NewQueue->size = 0;
//    StackInit(&(NewQueue->a));
//    StackInit(&(NewQueue->b));
//
//    return NewQueue;
//
//}
//
//void myQueuePush(MyQueue* obj, int x) {
//
//    assert(obj);
//
//    //每次都压在栈a中
//    StackPush(&(obj->a), x);
//
//    obj->size++;
//
//}
//
//int myQueuePop(MyQueue* obj) {
//    assert(obj);
//
//    int ret = 0;
//
//    //单一元素情况
//    if (obj->size == 1)
//    {
//        //最终数据存放默认在a栈中
//        ret = StackTop(&(obj->a));
//        StackPop(&(obj->a));
//
//        obj->size--;
//
//        return ret;
//    }
//    else
//    {
//        //将a栈中后size-1元素导入b栈
//        for (int i = obj->a.top ;i > 0 ; i--)
//        {
//            int x = StackTop(&(obj->a));
//            StackPop(&(obj->a));
//            StackPush(&(obj->b), x);
//        }
//        //此时栈顶元素则为队头元素
//        ret = StackTop(&(obj->a));
//        StackPop(&(obj->a));
//
//        //再将b栈中元素到导回a
//        for (int j = obj->b.top + 1; j > 0; j--)
//        {
//            int y = StackTop(&(obj->b));
//            StackPop(&(obj->b));
//            StackPush(&(obj->a), y);
//        }
//
//        obj->size--;
//    }
//    return ret;
//}
//
//int myQueuePeek(MyQueue* obj) {
//    assert(obj);
//
//    return StackBot(&(obj->a));
//}
//
//bool myQueueEmpty(MyQueue* obj) {
//    assert(obj);
//
//    if (obj->size)
//        return false;
//    else
//        return true;
//}
//
//void myQueueFree(MyQueue* obj) {
//    assert(obj);
//
//    //先释放子空间
//    StackDestroy(&(obj->a));
//    StackDestroy(&(obj->b));
//
//    free(obj);
//}
//
//
//int main()
//{
//    MyQueue* pq = myQueueCreate();
//    myQueuePush(pq ,1);
//    myQueuePush(pq, 2);
//    myQueuePush(pq, 3);
//    myQueuePush(pq, 4);
//
//    int x = myQueuePop(pq);
//    
//    myQueuePush(pq, 5);
//    x = myQueuePop(pq);
//    x = myQueuePop(pq);
//    x = myQueuePop(pq);
//    x = myQueuePop(pq);
//
//
//
//    return 0;
//}


typedef struct {
    int head;
    int tail;

    //子队列数据结构为数组
    int* Queue;
    int size;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    //创建MyCircularQueue
    MyCircularQueue* NewMCQ = malloc(sizeof(MyCircularQueue));
    if (NewMCQ == NULL)
    {
        perror("myCircularQueueCreate::malloc1");
        return NULL;
    }

    //初始化Queue;
    int* NewQueue = (int*)malloc(sizeof(int) * (k + 1)/*Queue多开一个空间有助于条件判断*/);
    if (NewQueue == NULL)
    {
        perror("myCircularQueueCreate::mallo2");
        return NULL;
    }
    NewMCQ->Queue = NewQueue;

    //初始化head tail size
    NewMCQ->head = NewMCQ->tail = 0;
    NewMCQ->size = k;

    return NewMCQ;
}

//声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);

    //判断队列是否已满
    if (myCircularQueueIsFull(obj))
        return false;
    else
    {
        (obj->Queue)[obj->tail] = value;

        if (obj->tail == obj->size)
            obj->tail = 0;
        else
            obj->tail++;

        return true;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);

    //判断队列是否为空
    if (myCircularQueueIsEmpty(obj))
        return false;
    else
    {
        if (obj->head == obj->size)
            obj->head = 0;
        else
            obj->head++;

        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);

    //判断队列是否为空
    if (myCircularQueueIsEmpty(obj))
        return -1;

    return (obj->Queue)[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);

    //判断队列是否为空
    if (myCircularQueueIsEmpty(obj))
        return -1;

    if (obj->tail == 0)
        return (obj->Queue)[obj->size];
    else
        return (obj->Queue)[obj->tail - 1];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);

    if (obj->head == obj->tail)
        return true;
    else
        return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);

    int pcur = obj->tail;

    if (pcur == obj->size)//当tail为表尾，+1回到表头
        pcur = 0;
    else
        pcur++;


    if (pcur == obj->head)
        return true;
    else
        return false;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);

    //释放子空间
    free(obj->Queue);

    free(obj);
    obj = NULL;
}


int main()
{
    MyCircularQueue* p = myCircularQueueCreate(2);
    myCircularQueueEnQueue(p, 4);
    int x = myCircularQueueRear(p);
    myCircularQueueEnQueue(p, 9);
    myCircularQueueDeQueue(p);
    x = myCircularQueueFront(p);
    myCircularQueueDeQueue(p);
    myCircularQueueDeQueue(p);
    myCircularQueueIsEmpty(p);
    myCircularQueueDeQueue(p);
    myCircularQueueDeQueue(p);
    myCircularQueueEnQueue(p, 6);
    myCircularQueueEnQueue(p, 4);






    return 0;
}
